/**
 *  @file DelUniqueValue.c
 *  @desc 在不带头结点的单链表中删除最小值结点的高效算法（支持唯一或多个最小值情况）
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-07-01 16:05
 *  @version 1.0
 */

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

// 定义单链表节点结构体
typedef struct node {
    int data;            // 节点存储的数据
    struct node *next;   // 指向下一个节点的指针
} node, *link;

// 创建一个新节点，赋值并初始化指针
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;  // 内存分配失败
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入一个节点（头插法）
// 注意：这里的 head 是指向链表第一个节点的指针（不是带头结点结构）
void insertHead(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = *head;
    *head = newNode;
}

// 在链表尾部插入一个节点（尾插法）
void insertTail(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    if (*head == NULL) {
        *head = newNode;  // 空链表，直接插入
        return;
    }
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// 打印链表中所有节点的值
void printList(link head) {
    if (head == NULL) return;
    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 释放整个链表的内存，避免内存泄漏
void destoryLink(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    while (cur != NULL) {
        link temp = cur;
        cur = cur->next;
        free(temp);
    }
    *head = NULL;
}

// 删除链表中唯一的最小值节点
// 要求：只遍历一遍找到最小值前驱，删除最小节点，无需额外变量
void delUniqueValue(link *head) {
    if (*head == NULL) return;

    link cur = *head;
    link minPre = NULL;  // 用于记录最小值节点的前驱
    while (cur->next != NULL) {
        if (cur->data > cur->next->data) {
            minPre = cur;  // 当前值比下一个大，说明更小的值出现在 next
        }
        cur = cur->next;
    }

    if (minPre == NULL) {
        // 最小值是头节点
        link temp = *head;
        *head = temp->next;
        free(temp);
    } else {
        // 最小值在非头节点位置
        link temp = minPre->next;
        minPre->next = temp->next;
        free(temp);
    }
}

// 删除链表中所有等于最小值的节点（最小值可能出现多个）
void delMultiValue(link *head) {
    // 如果链表为空，直接返回
    if (*head == NULL) return;

    // ========== 第一步：找出最小值 ==========
    link cur = *head;              // 当前遍历节点
    int minValue = cur->data;      // 假设第一个节点的值为最小值

    // 遍历链表，找出最小值
    while (cur->next != NULL) {
        if (cur->next->data < minValue) {
            minValue = cur->next->data;  // 更新最小值
        }
        cur = cur->next;  // 移动到下一个节点
    }

    // ========== 第二步：删除所有等于最小值的节点 ==========

    // -------- 先处理头节点可能等于最小值的情况 --------
    while (*head != NULL && (*head)->data == minValue) {
        link temp = *head;         // 保存当前头节点
        *head = temp->next;        // 头节点指向下一个节点
        free(temp);                // 释放被删除的节点
    }

    // -------- 删除链表中非头部的最小值节点 --------
    link temCur = *head;           // 当前节点，从第一个非最小值节点开始

    while (temCur != NULL && temCur->next != NULL) {
        if (temCur->next->data == minValue) {
            // 找到一个最小值节点，准备删除
            link delNode = temCur->next;
            temCur->next = delNode->next;  // 跳过该节点
            free(delNode);                 // 释放内存
        } else {
            temCur = temCur->next;         // 否则继续往后遍历
        }
    }
}


// 删除链表中所有值等于指定值的节点（可能是一个或多个）
void delValueByValue(link *head, int value) {
    // 如果链表为空，直接返回
    if (*head == NULL) return;

    // ===== 处理头节点中值等于目标值的情况 =====
    // 如果多个连续的头节点值等于 value，需要一个个删掉
    while (*head != NULL && (*head)->data == value) {
        link temp = *head;         // 暂存当前要删除的头节点
        *head = (*head)->next;     // 将头指针移向下一个节点
        free(temp);                // 释放原头节点的内存
    }

    // ===== 处理头节点之后的节点 =====
    // 此时 *head 指向的节点已经不是要删除的值，或者链表为空
    link cur = *head;              // 定义当前遍历指针，从头节点开始

    // 遍历链表，直到当前节点或其下一个节点为空
    while (cur != NULL && cur->next != NULL) {
        // 如果下一个节点的值是目标值
        if (cur->next->data == value) {
            link temp = cur->next;             // 保存要删除的节点
            cur->next = temp->next;       // 跳过目标节点
            free(temp);                        // 释放目标节点内存
        } else {
            cur = cur->next;                   // 否则继续遍历
        }
    }
}


// 修改链表中所有值等于 value 的节点，将它们的值改为 changeValue
void changeValueByValue(link *head, int value, int changeValue) {
    // 如果链表为空，直接返回
    if (*head == NULL) return;

    // 定义一个指针从头节点开始遍历
    link cur = *head;

    // 遍历整个链表
    while (cur != NULL) {
        // 如果当前节点的值等于目标值，则修改它
        if (cur->data == value) {
            cur->data = changeValue;
        }
        // 移动到下一个节点
        cur = cur->next;
    }
}


// 在链表中查找值为 value 的节点，返回该节点的指针；找不到返回 NULL
link findValue(link *head, int value) {
    // 如果链表为空，直接返回 NULL
    if (*head == NULL) return NULL;

    // 定义一个遍历指针，从头节点开始
    link cur = *head;

    // 遍历整个链表
    while (cur != NULL) {
        // 如果当前节点的值等于要查找的值，返回该节点
        if (cur->data == value) {
            return cur;
        } else {
            // 否则继续向下查找
            cur = cur->next;
        }
    }

    // 如果遍历完没有找到，返回 NULL
    return NULL;
}

// 销毁整个链表，释放所有节点的内存
void destroy(link *head) {
    // 如果链表为空，直接返回
    if (*head == NULL) return;

    // 定义当前遍历指针，从头节点开始
    link cur = *head;

    // 遍历整个链表
    while (cur != NULL) {
        link temp = cur;     // 保存当前节点
        cur = cur->next;     // 移动到下一个节点
        free(temp);          // 释放当前节点内存
    }

    // 最后将头指针设为 NULL，避免野指针
    *head = NULL;
}


// 反转链表

void reverse(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    *head = NULL;
    while (cur != NULL) {
        link temp = cur->next;
        cur->next = *head;
        *head = cur;
        cur = temp;
    }

}

// 主函数：测试用例
int main() {
    link head = NULL;
    // 插入若干节点，构建测试链表
    insertTail(&head, 1);   // 尾部部插入 1
    insertTail(&head, 1);   // 尾部部插入 1
    insertTail(&head, 2);   // 插入 2
    insertTail(&head, 3);   // 插入 3
    // destroy(&head);

    printList(head);
    reverse(&head);
    printList(head);


    //
    // // insertTail(&head, 0); // 如有需要可测试尾插
    //
    // // delUniqueValue(&head); // 测试删除唯一最小值节点
    //
    //

    //
    // destoryLink(&head);       // 释放所有节点，防止内存泄漏

    return 0;
}
